#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
typedef long long ll;
using namespace std;


//class Solution {
//public:
//    vector<int> findBall(vector<vector<int>>& grid) {
//        int n = grid.size(), m = grid[0].size();
//        vector<int> ans;
//        for (int i = 0; i < m; i++) {
//            int y = i;
//            bool fg = 0;
//            for (int j = 0; j < n; j++) {
//                if (grid[j][y] == 1) {
//                    if (y+1>=m||grid[j][y] + grid[j][y + 1] == 0) {
//                        fg = 1;
//                        ans.push_back(-1);
//                        break;
//                    }
//                    y++;
//                }
//                else {
//                    if (y-1<0||grid[j][y] + grid[j][y -1] == 0) {
//                        fg = 1;
//                        ans.push_back(-1);
//                        break;
//                    }
//                    y--;
//                }
//            }
//            if(!fg)
//                ans.push_back(y);
//        }
//        return ans;
//    }
//};
//
//int main() {
//    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//    vector<vector<int>> grid = { {1,1,1,-1,-1}, {1,1,1,-1,-1}, {-1,-1,-1,1,1}, {1,1,1,1,-1}, {-1,-1,-1,-1,-1} };
//    Solution sol;
//    vector<int> result = sol.findBall(grid);
//    for (int x : result) {
//        cout << x << " ";
//    }
//    cout << endl;
//    return 0;
//}

//class Solution {
//public:
//    int ans;
//    bool check(int m, vector<int>& ne, int b, int t) {
//        int n = ne.size();
//        for (int i = 1; i < n; i++) {
//            if (ne[i] >= m && t > 0)
//                t--;
//            else {
//                if (b >= ne[i])
//                    b -= ne[i];
//                else {
//                    if (i + t >= ans)
//                        return ans = i + t - 1;
//                    else
//                        return false;
//                }
//            }
//        }
//        return n - 1;
//    }
//    int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
//        int n = heights.size();
//        vector<int> ne(n);
//        for (int i = 1; i < n; i++) {
//            ne[i] = max(0, heights[i] - heights[i - 1]);
//        }
//        check(0, ne, bricks, ladders);
//        int l = 0, r = ranges::max(heights), m;
//        while (l < r) {
//            m = (l + r + 1) >> 1;
//            if (check(m, ne, bricks, ladders))
//                    l = m;
//            else
//                    r = m - 1;
//        }
//        return ans;
//    }
//};

//class Solution {
//public:
//    bool check(int m, vector<int> ne, int b, int t) {
//        sort(ne.begin(), ne.begin() + m+1);
//        for (int i = m; i >= 0; i--) {
//            if (t > 0)
//                t--;
//            else {
//                if (b >= ne[i])
//                    b -= ne[i];
//                else
//                    return false;
//            }
//        }
//        return true;
//    }
//
//    int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
//        int n = heights.size();
//        vector<int> ne(n);
//        for (int i = 1; i < n; i++) {
//            ne[i] = max(0, heights[i] - heights[i - 1]);
//        }
//        int l = 0, r = n-1, m;
//        while (l < r) {
//            m = (l + r + 1) >> 1;
//            if (check(m, ne, bricks, ladders))
//                l = m;
//            else
//                r = m - 1;
//        }
//        return l;
//    }
//};
//
//int main() {
//    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//    vector<int> heights = { 4,12,2,7,3,18,20,3,19 };
//    int bricks = 10;
//    int ladders = 2;
//    Solution sol;
//    int result = sol.furthestBuilding(heights, bricks, ladders);
//    cout << "Furthest building: " << result << endl;
//    return 0;
//}

//int n, m;
//struct edge {
//	int u, v, t;
//}e[200005];
//
//int f[20005];
//int find(int x) {
//	return f[x] == x ? x : (f[x] = find(f[x]));
//}
//
//bool cmp(const edge& a,const edge& b) {
//	return a.t < b.t;
//}
//
//
//int main() {
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	cin >> n >> m;
//	if (n == 1) {
//		cout << 0 << '\n';
//		return 0;
//	}
//	for (int i = 1; i <= n; i++) {
//		f[i] = i;
//	}
//	for (int i = 1,u,v,t; i <= m; i++) {
//		cin >> u >> v >> t;
//		e[i] = { u,v,t };
//	}
//	int tot = n, ans = -1;
//	sort(e + 1, e + 1 + m, cmp);
//	for (int i = 1; i <= m; i++) {
//		int fu = find(e[i].u), fv = find(e[i].v);
//		if (fu != fv)f[fu] = fv, tot--;
//		if (tot == 1) {
//			ans = e[i].t;
//			break;
//		}
//	}
//	cout << ans << '\n';
//	return 0;
//}